The invention relates to a method and a device for the resequencing of data messages or data packets which are transferred from an input port to an output port in a network.
In processing operations of data messages which are being transferred in a network it may for the processing be necessary or very advantageous to distribute an incoming stream of data messages over several different parallel processing units such as servers. A processing unit may in certain cases for instance not have time to process all the data messages transferred. Then, of course a more rapid processing unit can be used, when it is possible or not too costly, but as alternative several parallel units can be used. In order to utilize several processing units in a way which is as efficient as possible a dynamic distribution of the data packets is required over the available processing units. It can mean that for instance the unit which at a considered instant has the lowest load will obtain the next message which will arrive to the network in order to be processed. Another possibility is to randomly distribute the incoming messages over the available processing units. A great advantage of this dynamic distribution is further achieved if the load from a multitude of input ports is dynamically distributed on several processing units. Then a statistic profit will arise resulting in that the total server capacity can be substantially reduced compared to the case where each input port is associated with a selected, predetermined processing unit.
However, the stream of data messages most often consists of messages from different sources which are to be delivered to their destinations in the same sequential order as the messages arrived. In a dynamic distribution it cannot be safe-guarded that the correct sequential order is maintained since it is not at all sure that the processing units work equally fast. In order to be able to still perform this dynamic load distribution the correct sequential order of the individual data messages must in some way be restored, at least before the delivery and transmission from the network. The conventional method of solving this problem is that each message is marked with a sequential number when the message is received at an input port of the network and that a resequencing is performed in the delivery from the network by means of the sequential numbers of the forwarded data packets, these sequential numbers before the forwarding being removed from the data messages.
The requirement of a correct sequential order is in this case valid only for pairs of a source and a destination. Sources and destinations are conventionally identified with unique addresses in the network and in the data messages. At the input port of the network each incoming message must be assigned a sequential number or order number which indicates the sequential position of the message in relation to previously arrived messages from the same source, in order that it will be possible to restore the sequential order of the data messages at the output port. This assigned sequential number must therefore in the input port be taken from a memory and from a list stored therein which is established by the logic circuits in the input port and contains the current, next following sequential number for each possible combination of sources and destinations, or at least so many such pairs of sources and combinations, which up to the reception of this data packet have been encountered in data packets arrived to the input port. A very long list of such combinations of sources and destinations together with the current sequential numbers must then in many cases be stored and administered and at the arrival of a new data packet half the list must be searched, in an average, in order to find the same combination of source and destination which is valid for the received data packet. Such a list will then easily comprise hundreds or thousands of records among which a searching operation would require a time period having an unacceptable length.
The patent U.S. Pat. No. 5,127,000 describes a packet distributing network with automatic resequencing. If the packets follow different paths through the network, they may be subjected to different delays and thereby the packets can arrive to the output port in a wrong sequential order. The patent discloses a method of restoring the sequential order of the packets at the output port. According to the document a circuit is provided providing the packet with a "time stamp" at the input port of the network. Before the output the time delay is detected which the network has caused to the packet. The packet is delayed even more so that the total delay will be equal to a predetermined value. Thereby the total delay through the network will be approximately constant and the packets are delivered to the output port in the same sequential order as they were delivered to the input port.
The patent U.S. Pat. No. 4,807,224 is related to a system for distributing data in the shape of packets to a large number of receivers. A central unit sequentially issues packets which among other things contain an information field and a sequential number, to a number of receivers and back-up units. Each receiver copies the data packets to a buffer in order to be able to select portions which are of interest to the receiver. If the receiver discovers that a packet is missing it can be taken from a back-up unit. A packet is considered missing if a predetermined time period has elapsed since the previous packet was received or if a packet having a wrong sequential number arrives. The receiver can thus restore the sequential order when transmission errors occur.
The patent U.S. Pat. No. 4,630,260 relates to a method for coupling packets through a packet distributing network with a maintained sequential order at the output side of the network. The sequential order is maintained simply by the method that packets having the same address cannot be transmitted in parallel over the same node.
The patent U.S. Pat. No. 5,173,897 is concerned with an ATM-network where the successive cells of a logical connection are routed to the output by as many different paths as possible. At the input end the consecutive sequence numbers are allocated to the cells. At the output end each cell is held until it is certain that no older cell can be buffered in the switching area of the network.